package everyday;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/8/19 21:38
 * 接雨水
 * https://leetcode.cn/problems/trapping-rain-water/description/
 */
public class Solution42 {

    // 方法一 按列求, 每次找到当前列左侧和右侧最高列的较小值, 进行分类讨论
    // 时间复杂度 O(n^2) 空间复杂度 O(1)
    public int trap01(int[] height) {
        int sum = 0;
        //最两端的列不用考虑，因为一定不会有水。所以下标从 1 到 length - 2
        for (int i = 1; i < height.length - 1; i++) {
            int max_left = 0;
            //找出左边最高
            for (int j = i - 1; j >= 0; j--) {
                if (height[j] > max_left) {
                    max_left = height[j];
                }
            }
            int max_right = 0;
            //找出右边最高
            for (int j = i + 1; j < height.length; j++) {
                if (height[j] > max_right) {
                    max_right = height[j];
                }
            }
            //找出两端较小的
            int min = Math.min(max_left, max_right);
            //只有较小的一段大于当前列的高度才会有水，其他情况不会有水
            if (min > height[i]) {
                sum = sum + (min - height[i]);
            }
        }
        return sum;
    }

    // 方法二 使用单调栈
    // 时间复杂度 O(n) 空间复杂度 O(n)
    public int trap02(int[] height) {
        // 边界处理
        if (height == null || height.length <= 2) {
            return 0;
        }
        // 使用单调不增栈, height 作为右墙, 依次入栈
        // 在右墙出现了比栈顶更高的元素时, 说明墙的左侧形成了低洼处, 就需要结算一部分水
        int water = 0;
        Deque<Integer> stack = new LinkedList<>(); // 栈中存的是左右墙与低洼处的索引位置
        for (int right = 0; right < height.length; right++) {
            while (!stack.isEmpty() && height[right] > height[stack.peek()]) {
                // 低洼处弹出, 并尝试计算当前位置的水
                int bottom = stack.pop();
                // 判断左墙是否存在, 如果只有右墙 + 低洼处而没有左墙是白搭的
                if (stack.isEmpty()) {
                    break;
                }
                // 计算水
                int left = stack.peek(); // 左墙的位置
                int leftHeight = height[left]; // 左墙的高度
                int rightHeight = height[right]; // 右墙的高度
                int bottomHeight = height[bottom]; // 低洼处的高度
                water += (right - left - 1) * (Math.min(leftHeight, rightHeight) - bottomHeight);
            }
            // 先 pop 后再 push 保证是单调不增
            stack.push(right);
        }
        return water;
    }
}
